/*
 * Copyright (C), 2015-2018
 * FileName: Solution015
 * Author:   zhao
 * Date:     2018/11/9 19:45
 * Description: 15. 三数之和
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈15. 三数之和〉
 *
 * @author zhao
 * @date 2018/11/9 19:45
 * @since 1.0.1
 */
public class Solution015 {

    /**************************************
     * 题目
     给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
     找出所有满足条件且不重复的三元组。

     注意：答案中不可以包含重复的三元组。

     例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     满足要求的三元组集合为：
     [
     [-1, 0, 1],
     [-1, -1, 2]
     ]
     **************************************/

    /**************************************
     *
     * 想法：
     *      1.暴力破解：
     *          嵌套三层循环
     *              注意：遍历结果是否相同
     *              时间复杂度比较高
     *      2.先排序，以0位分割点，再进行计算
     *          找到负数最大位置、正数最小位置、0的个数
     *              0超过三个，则肯定有个答案是000
     *              当没有负数或者没有正数的时候，直接返回
     *          滑动列表的方法
     *              以负数们为循环（最大值为数最大位置）
     *                  负数的绝对值为目标
     *                  双指针 left为下一个数，right为最大长度
     *                  两数相加小于目标，则right左移，否则left右移
     *                  通过nums[leftIndex] == nums[leftIndex + 1] 控制重复数据
     *                      注意这里数组越界，要价格left<right判断
     * 我的做法
     *      超过99%的测试案例
     *      时间复杂度：复杂度最高的应该就是排序算法了Arrays.sort(nums)
     *      空间复杂度：接收结果List<List<Integer>> result
     * 代码执行过程：
     *          找到负数最大位置、正数最小位置、0的个数
     *              0超过三个，则肯定有个答案是000
     *              当没有负数或者没有正数的时候，直接返回
     *          滑动列表的方法
     *              以负数们为循环（最大值为数最大位置）
     *                  负数的绝对值为目标
     *                  双指针 left为下一个数，right为最大长度
     *                  两数相加小于目标，则right左移，否则left右移
     *                  通过nums[leftIndex] == nums[leftIndex + 1] 控制重复数据
     *                      注意这里数组越界，要价格left<right判断
     * 总结：
     *      1. 想到了排序
     *      2. 没有想到使用滑动列表
     *      3. 在书写代码的时候，很多细节没有考虑到，比如重复
     * ***********************************/
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 1) {
            return Collections.EMPTY_LIST;
        }

        Arrays.sort(nums);
        int target = 0;
        int targetCount = 0;
        // 负数最大索引
        int spilt0 = -1;
        // 正数最小索引
        int spilt2 = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < target) {
                spilt0 = i;
            } else if (nums[i] == target) {
                targetCount++;
            } else if (nums[i] > target) {
                spilt2 = i;
                break;
            }
        }

        // 出现超过三个0，就肯定有一个答案是000
        List<List<Integer>> result = new ArrayList<>();
        if (targetCount >= 3) {
            List<Integer> list = new ArrayList<>();
            list.add(0);
            list.add(0);
            list.add(0);
            result.add(list);
        }

        // 这种时候只有非负数，或者只有非正数，除了000，否则是凑不齐的
        if (spilt0 == -1 || spilt2 == -1) {
            // 这里有可能全部都是0,不然就肯定无法满足条件
            return result;
        }

        // 当整体数据有正有负，就遍历负数就好
        // 然后使用滑动列表
        // 以负数的绝对值为目标，后面2数相加小于目标，则左移，否则右移
        for (int i = 0; i <= spilt0; i++) {
            // 如果和之前那个数据相同，则会是重复事件
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int val = nums[i] * -1;
            int leftIndex = i + 1;
            int rightIndex = nums.length - 1;
            while (leftIndex < rightIndex) {
                int tmpVal = nums[leftIndex] + nums[rightIndex];
                if (tmpVal > val) {
                    rightIndex--;
                } else if (tmpVal < val) {
                    leftIndex++;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[leftIndex]);
                    list.add(nums[rightIndex]);
                    result.add(list);
                    // 用nums[leftIndex] == nums[leftIndex + 1]控制重复
                    while (leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex + 1]) {
                        leftIndex++;
                    }
                    while (leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex - 1]) {
                        rightIndex--;
                    }
                    leftIndex++;
                    rightIndex--;
                }
            }
        }
        return result;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<List<Integer>> better(int[] nums) {
        if (nums.length < 3) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        int minValue = Integer.MAX_VALUE;
        int maxValue = Integer.MIN_VALUE;
        int negSize = 0;
        int posSize = 0;
        int zeroSize = 0;
        for (int v : nums) {
            if (v < minValue) {
                minValue = v;
            }
            if (v > maxValue) {
                maxValue = v;
            }
            if (v > 0) {
                posSize++;
            } else if (v < 0) {
                negSize++;
            } else {
                zeroSize++;
            }
        }
        if (zeroSize >= 3) {
            res.add(Arrays.asList(0, 0, 0));
        }
        if (negSize == 0 || posSize == 0) {
            return res;
        }
        if (minValue * 2 + maxValue > 0) {
            maxValue = -minValue * 2;
        } else if (maxValue * 2 + minValue < 0) {
            minValue = -maxValue * 2;
        }

        int[] map = new int[maxValue - minValue + 1];
        int[] negs = new int[negSize];
        int[] poses = new int[posSize];
        negSize = 0;
        posSize = 0;
        for (int v : nums) {
            if (v >= minValue && v <= maxValue) {
                if (map[v - minValue]++ == 0) {
                    if (v > 0) {
                        poses[posSize++] = v;
                    } else if (v < 0) {
                        negs[negSize++] = v;
                    }
                }
            }
        }
        Arrays.sort(poses, 0, posSize);
        Arrays.sort(negs, 0, negSize);
        int basej = 0;
        for (int i = negSize - 1; i >= 0; i--) {
            int nv = negs[i];
            int minp = (-nv) >>> 1;
            while (basej < posSize && poses[basej] < minp) {
                basej++;
            }
            for (int j = basej; j < posSize; j++) {
                int pv = poses[j];
                int cv = 0 - nv - pv;
                if (cv >= nv && cv <= pv) {
                    if (cv == nv) {
                        if (map[nv - minValue] > 1) {
                            res.add(Arrays.asList(nv, nv, pv));
                        }
                    } else if (cv == pv) {
                        if (map[pv - minValue] > 1) {
                            res.add(Arrays.asList(nv, pv, pv));
                        }
                    } else {
                        if (map[cv - minValue] > 0) {
                            res.add(Arrays.asList(nv, cv, pv));
                        }
                    }
                } else if (cv < nv) {
                    break;
                }
            }
        }
        return res;
    }

}
